#include <stdlib.h>
#include <string.h>
//Link:https://leetcode-cn.com/problems/delete-operation-for-two-strings/description/
//https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings/description/
int max(int a, int b) {
    return a>b ?a: b;
}

int minDistance(char* word1, char* word2) {
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    /***********************
    dp[i][j]: w1[0---i-1], w2[0---j-1]的最长公共子序列长度
    递推式:
    dp[i][j] = {
        0                           when i==0 || j==0
        dp[i-1][j-1]+1              when w1[i-1]==w2[j-1]
        max(dp[i][j-1], dp[i-1][j]) when w1[i-1]!=w2[j-1]
        
    }
    空间压缩:
    dp[j]: dp[i][j]
    ************************/
    int *dp = calloc(len2+1, sizeof(int));
    int i,j;
    for(j=0; j<=len2; j++)
        dp[j] = 0; //dp[0][j] = 0;
    
    int prej_one; //dp[i-1][j-1]
    int tmp; //for next prej_one
    for(i=1; i<=len1; i++) {
        prej_one = 0; //dp[i-1][1-1]
        for(j=1; j<=len2; j++) {
            tmp = dp[j]; //dp[i-1][j]
            if(word1[i-1]==word2[j-1])
                //dp[i][j] = dp[i-1][j-1]+1;
                dp[j]= prej_one+1;
            else
                //dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
                dp[j] = max(dp[j-1], dp[j]);
            prej_one = tmp;
        }
                
    }
    
    int res = len1+len2 - dp[len2]*2;  // dp[len1][len2]
    free(dp);
    return res;
    
}
